#include <map>
#include <ctime>
#include <cstdio>
#include <random>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef __int128 lll;
ll n,ans;
map<ll,ll>mp;
int i,j,k,m,x,y,t,T;
ll mi(ll x,ll y,ll mo){
    if (y==0)return 1;
    ll t=mi(x,y>>1,mo);
    t=(lll)t*t%mo;
    if (y&1)t=(lll)t*x%mo;
    return t;
}
ll randint(ll l, ll r = 0){
    static mt19937 eng(time(0));
    if (l>r)swap(l,r);
    uniform_int_distribution<ll> dis(l, r);
    return dis(eng);
}
ll rand(ll x,ll c,ll mo){return ((lll)x*x+c)%mo;}
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
int MillerRabin(ll x){
    int cnt=10;
    if (x==2||x==3)return 1;
    ll d=x-1,s=0;while (d%2==0)d>>=1,s++;
    while (cnt--){
        ll a=randint(2,x-2);
        a=mi(a,d,x);
        if (a==1||a==x-1)continue;
        for (i=1;i<s;i++){
            a=(lll)a*a%x;
            if (a==x-1)break;
            if (a==1)return 0;
        }
        if (a!=x-1)return 0;
    }
    return 1;
}
ll PollardRho(ll x){
    if (x<ans)return x;
    if (x==4)return 2;
    if (mp[x])return ans=max(ans,mp[x]);
    if (MillerRabin(x))return ans=max(ans,mp[x]=x);
    while (1){
        ll a=randint(0,x-1);
        ll baby=rand(0,a,x),giant=rand(rand(0,a,x),a,x);
        int k=0;
        while (baby!=giant){
            ll d=1;
            for (int i=0;i<(1<<k);i++){
                ll te=(lll)d*abs(giant-baby)%x;
                if (te==0)break;
                d=te;
                baby=rand(baby,a,x);giant=rand(rand(giant,a,x),a,x);
            }
            d=gcd(d,x);if (k<7)k++;
           if (d>1)return mp[x]=max(PollardRho(d),PollardRho(x/d));
        }
    }
}
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%lld",&n);ans=0;
        if (MillerRabin(n))printf("Prime\n");
        else printf("%lld\n",PollardRho(n));
    }
    return 0;
}
